﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Runtime.Remoting.Messaging;
using System.Security.Cryptography;
using System.Text;
using System.Threading.Tasks;

namespace ChineseRemainderTheorem.Core
{
    public class BigIntegerRandom : IBigIntegerRandom
    {
        private readonly Random _random = new Random();

        private static readonly BigInteger Two = new BigInteger(2);

        /// <summary>
        /// Check a number on the prime by formula 2^(n-1)=1(mod n)
        /// </summary>
        /// <param name="a"></param>
        /// <param name="n"></param>
        /// <returns></returns>
        private static bool Witness(BigInteger a, BigInteger n)
        {
            // split number n-1=2^t*u where u - odd
            BigInteger u = n - BigInteger.One;
            int t = 0;

            // check root in trivial
            for (t = 0; u.IsPowerOfTwo; t++)
            {
                u = u/Two;
            }
            // В результате после t итераций мы либо вычисляем a^(n-1), либо находим нетривиальные корни
            
            BigInteger[] x = new BigInteger[t + 1];
            x[0] = BigInteger.ModPow(a, u, n);
            // to not calculate in each iteration
            BigInteger nMinusOne = n - BigInteger.One;
            for (int i = 1; i <= t; i++)
            {
                x[i] = BigInteger.ModPow(x[i - 1], Two, n);
                if (x[i] == BigInteger.One && x[i - 1] != BigInteger.One && x[i - 1] != nMinusOne)
                {
                    return true;
                }
            }
            if (x[t] != BigInteger.One)
            {
                return true;
            }
            return false;
        }

        private bool IsPrimeMillerRabin(BigInteger n, int s)
        {
            BigInteger pred = BigInteger.Zero;
            for (int j = 0; j < s; j++)
            {
                BigInteger a = Next(n);
                while (a == pred)
                {
                    a = Next(n);
                }
                if (Witness(a, n))
                {
                    return false;
                }
            }
            return true;
        }

        public BigInteger Next(int size)
        {
            byte[] buffer = new byte[size];
            _random.NextBytes(buffer);
            // positive value
            buffer[buffer.Length - 1] &= 0x7f;
            return new BigInteger(buffer);
        }

        public BigInteger Next(BigInteger n)
        {
            byte[] bytes = n.ToByteArray();
            BigInteger r;
            do
            {
                _random.NextBytes(bytes);
                bytes[bytes.Length - 1] &= 0x7f;
                r = new BigInteger(bytes);
            } while (r >= n);
            return r;
        }

        public BigInteger Next(BigInteger a, BigInteger b)
        {
            return Next(b - a) + a;
        }

        public bool NextPrime(BigInteger a, BigInteger b, out BigInteger prime)
        {
            int i = 0;
            BigInteger last = BigInteger.One;
            while (i < 10000)
            {
                BigInteger temp = Next(a, b);
                if (IsPrimeMillerRabin(temp, 100))
                {
                    prime = temp;
                    return true;
                }
                else
                {
                    last = temp;
                    i++;
                }
            }
            prime = BigInteger.MinusOne;
            return false;
        }
    }
}
